package com.springboot.java.design.sort;

/**
 *  快速排序
 *      思路： 选取数组的最后一个元素作为pivot
 *            从第一个元素开始和pivot比较
 *            比pivot小,放在小于区间并排序
 *            比pivot大,放在大于区间并排序
 *            递归重复这个选取分区点并比较排序的过程
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,6,1,8,2,0};
        quickSort(arr, 0, arr.length -1);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }

    /**
     *  快排
     * @param a
     */
    public static void quickSort(int[] a, int offset, int end){

        if(offset >= end){
            return;
        }

        // 分区点索引
        int pivot = pivotIndex(a, offset, end);

        quickSort(a, offset, pivot-1);
        quickSort(a, pivot+1, end);

    }


    /**
     *  计算low和high区间的中间索引
     * @param a       数组
     * @param offset  起始索引
     * @param end     结束索引
     * @return
     */
    public static int pivotIndex(int[] a, int offset, int end){

        int pivot = a[end];

        // j 索引指向的是high区间的第一个元素
        int j = offset;
        // 遍历high区间
        for (int i = offset; i < end; i++) {
            if(a[i] < pivot){
                // 需要交换
                if(i != j){  // 避免索引一致时做无谓的交换
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                }
                j++;
            }
        }

        // 交换完 需要将pivot 放到j的位置
        int temp = a[j];
        a[j] = pivot;
        a[end] = temp;

        return j;
    }

}
